import org.omg.PortableInterceptor.INACTIVE;

import java.awt.*;
import java.io.ObjectOutputStream;
import java.util.*;

//{-1, 2, 4, 3, -6, 7} 两个不相交的子数组的最大值
public class Main {

    private static int sum = 0;

    public static void main(String[] args) {
        int[] nums = {-1, 2, 4, 3, -6, 7};
        System.out.println(maxNum(nums));
    }

    public static int maxNum(int[] nums) {
        int[] maxL = new int[nums.length];
        int[] maxR = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            maxL[i] = maxNum(nums, 0, i);
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            maxR[i] = maxNum(nums, i, nums.length - 1);
        }
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            //左边最大子数组和+右边最大子数组和
            max = Math.max(max, maxL[i - 1] + maxR[i]);
        }
        return max;
    }

    //数组最大子数组和
    public static int maxNum(int[] nums, int lo, int hi) {
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = lo; i <= hi; i++) {
            cur += nums[i];
            max = Math.max(max, cur);
            cur = cur < 0 ? 0 : cur;
        }
        return max < 0 ? 0 : max;
    }
}
